

n = 1509703035823330868869834522024092120362026376215083543284745630793308975796190467602788829812297901857932935039025089268627466912654089700188742017629622065783672394888359969707651240459837020672860929988757777030422769024286740614005717037074268883573110930153062785087729053447171701253209971379929079347835021751672558512393510724289890183585413478294827821311845502534023382207957546333364850200633897723439835808211061193076892436044104348373486494641376389
d = 100979306232312695245700516917839918110768588401231931106393736034106454368084761256266189220093118416948559514884440649080921184917841919093078821064183722506780656524852279972290965094998707911997353762800312689241799367933592922491408264361152808814318681758462162634135730009606801553694049130523417875109
c = 454123376260518706668542553137676139521592440006085495404351831846295926902153925321446092154967474652101464587395537082757989754856425391928305101514843572153411118960509564828565177894781670685448363111260515937752238218399127935714819955614213979736317795119251691182610359710855263892329541043237906207898972666595471408120576216937566087628620977516560432010102360661962038034497683976798523794858005197890412841899607522392865669274636150630432380289563966
p = 11950866836661074605861258735756625004205346357223809487017358111173811555644650512602794406276701550166038794297786309595839100388244193660047984677501683
q = 10570431442477911828938550659496955709294910257519621502414731438107318951081942626527703275733466851742056735246739982814503063038040207067035611990655101


k=n*d-1
k //= 2
a=pow(3,k,n)
import libnum
q=libnum.gcd(a-1,n)
print(q)
p=n//q
print(p)
